//
//  Vector_find.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/5.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

/// 对于无序向量来说 Element只需要能判等
/// 对于有序向量来说 Element必须是可比较的
extension Vector where Element: Equatable {
    
    public func find(_ element: Element) -> Index {
        return _find(element, from: 0, to: _size)
    }
    
    public func find(_ element: Element, at range: CountableRange<Index>) -> Index {
        return _find(element, from: range.lowerBound, to: range.upperBound)
    }
    
    public func find(_ element: Element, at range: CountableClosedRange<Index>) -> Index {
        return _find(element, from: range.lowerBound, to: range.upperBound.advanced(by: 1))
    }
    
    /// 无序向量查找，返回元素命中的位置
    /// 无论是否匹配都会返回一个确定的位置
    /// 如果未有匹配元素，返回 -1
    /// Note: `to` is not include(a.k.a CountableRange)
    func _find(_ element: Element, from startIndex: Index, to endIndex: Index) -> Index {
        precondition(startIndex >= 0 && startIndex <= endIndex, "Index不能为负数且startIndex不能大于endIndex")
        precondition(endIndex <= self.endIndex, "指定区间(\(startIndex)-\(endIndex))超过\(self)的容量")
        for i in startIndex..<endIndex {
            if _storage[i] == element { return i }
        }
        return NotFound
    }
}
